1. Field of the Invention
The present invention generally relates to computer communication networks and, more particularly, to a new concepts for controlling access to high data rate ring or unidirectional bus networks. More specifically, the invention is directed to high data rate networks capable of supporting a variety of traffic types, including voice, video and computer data transferred both asynchronously and synchronously with varying bandwidths.
2. Description of the Prior Art
Communication networks have made possible distributed processing between all classes of computers from super computers to personal computers, promoting greater efficiency and productivity. Both baseband and broadband networks have been developed. Various topologies including star, ring and bus based networks have been implemented. Access control to the networks is required to permit a node to transmit its information on to the network without interfering with or corrupting information traveling on the network.
In a parallel development, multi-media systems are gaining increasing adherents. Such systems support high-quality images, audio, animation and full-motion video. Voice annotations added to business presentations and free-form database queries made through a graphic user interface (GUI) are among the many and diverse advantages of multimedia systems. To support multi-media systems, high data rate networks are required for all types of traffic including voice, video and computer data. Voice and video are referred to as synchronous traffic since new data to transmit occurs at a prescribed rate. Computer data is called asynchronous since its time and rate of occurrence are irregular. Synchronous traffic demands a different quality of service than asynchronous traffic because it requires guaranteed access of the network for fixed blocks at a fixed rate.
Mechanisms proposed for supporting integrated traffic within the access protocol can be divided into two basic categories. The first attempts to provide a mechanism within the framework of the access protocol to support synchronous and asynchronous traffic. This usually results in some type of priority or control system which regulates normal access so that all synchronous traffic can be submitted within a limited time scope and repeated periodically. A second type of support for integrated traffic uses two media access mechanisms in a single network. In this class, uniframe techniques have been used almost exclusively to provide for the synchronous traffic. Uniframe is based upon the 125 microsecond (.mu.sec) telephone virtual circuit frame and supplies a fixed number of 8-bit slots. Each slot is reserved for a synchronous call circuit or a video circuit. Asynchronous traffic uses either the empty slots or is provided a space after one uniframe frame has completed and before the next one begins.
More than sixty different media access protocols for networks operating in the range of 50 to 5000 Mbps have been reported by M. Skov in "Implementation of Physical and Media Access Protocols for High Speed Networks", IEEE Communications Magazine, June 1989, pp. 45-53. At 100 Mbps and above, most networks use fiber optical media because of the signal attenuation advantage and the higher data rate capability. Because of the inability to construct low loss taps other than star couplers, fiber optical networks are usually point-to-point. In many cases, this results in networks that are either rings or unidirectional buses with each node containing at least one transmitter and receiver with each node forwarding messages, either those received from other nodes on the network or generated at the node, to the succeeding or a down stream node.
Many of these network systems use demand assignment access protocol. Implementation of the protocol concept can take many forms including token ring, like the Fiber Distributed Data Interface (FDDI), where a node must capture the token before it is allowed to send its messages; slotted ring, such as the Cambridge Ring, where slots are tested for empty or full status; "attempt and defer", as implemented, for example, by Metrocore, where a node starts transmitting while the slot is being tested and aborts if the slot is full; polled access; or a slotted reservation system, such as Distributed Queue, Dual Bus (DQDB), where the need for free slots are sent to the upstream nodes in an effort to maintain fair access for all nodes. One feature of all demand assignment access protocols is that they are contention or collision free; that is, it is known at the time which they start transmitting a queued message that they will not interfere with messages on the network for the period which they are transmitting. For example, in a slotted system, this would be the time period of a slot. Operations for these and related systems are discussed by M. Skov, supra, and other papers including the Cambridge Ring described by M. Zafirovic-Vukotic, I. G. Niemegeers and D. S. Valk in "Performance Analysis of Slotted Ring Protocols in HSLANs", Jour. on Selected Areas in Communications, vol. 6, no. 6, July 1988, pp. 1011-1023; Expressnet and Fastnet described by F. A. Tobaji and M. Fine in "Performance of Unidirectional Broadcast Local Area Networks Expressnet and Fastnet", IEEE Jour. on Selected Areas in Communications, vol. SAC-1, no. 5, Nov. 1983, pp. 913-925; and DQDB (formerly QPSX) described by R. M. Newman, Z. L. Budrikis and J. L. Hullett in "The QPSX Man", IEEE Communications Magazine, vol. 26, no. 4, April 1988, pp. 20-28.
One form of a demand assignment access protocol, the register-insertion system, described by W. Hilal and M. T. Liu in "Analysis and Simulation of the Registration-Insertion Protocol", Proc. of Computer Networking Symposium, Dec. 10, 1982, pp. 91-100, and M. T. Liu, W. Hilal and B. H. Groomes in "Performance Evaluation of Channel Access Protocols for Local Computer Networks", Proc. Computer Networks, Compcon '82, Sept. 2-23, 1983, pp. 417-426, uses a buffer to assist in controlling access. When a node wishes to transmit, it inserts its empty buffer in the incoming stream link so that any incoming message may be saved until it completes transmission of its queued message. It then empties the buffer, forwarding the delayed message. It must have an empty buffer before it can start the transmission process. Buffer size can limit the size of the messages.
In slotted systems, long messages must be broken into slot size proportions contributing to fracture of the message and wasted network capacity, since the slot size selected is always a compromise over the wide range of message traffic size. In addition, slotting or polling causes delay even at low loads because a queued message must wait until the head of a slot or the cessation of the polling before it can start transmitting. The register insertion method can slow travel for messages on the network. Even though demand assignment access protocols provide full utilization at capacity loads, recent studies indicate that reservation systems have fairness difficulties when servicing nodes at the ends of the bus under high load conditions. See K. Maly, L. Zhang and D. Game, "Fairness Problems in High-Speed Networks", Old Dominion University, Computer Science Dept., TR-90-15, Mar. 1990. Other demand access systems may use a token, like FDDI, but waiting for the token to rotate can cause increased access delay, especially in longer length and higher data rate networks. See F. Ross, "FDDI--A Tutorial", IEEE Transactions on Communications, vol. 24, no. 5, May 1986, pp. 10-17, and the draft of the proposed American National Standard entitled "FDDI Token Ring Media Access Control (mac)", asc .times.3t9.5 rev. 10, Feb 28, 1986. Most demand assignment systems can be considered to operate under "attempt and defer" conditions although register-insertion has an "attempt and hold" mode as well.
The adaptive assignment or random access protocols use a somewhat different form of access from contention free protocols. These systems, like contention free protocols, sense the presence or absence of a message on the network. If the network is free, the node can begin to transmit. However, sensing a free network does not assure collision free access for the period of time necessary to transmit the message. If a collision occurs, the information on the network is corrupted. The nodes which have transmitted messages must be able to detect the fact that a collision has occurred and retransmit their messages when the network is again idle. These systems are generally classified as Carrier Sensed Multiple Access (CSMA). Ethernet, a shared channel system, is designed to detect collisions (CD) shortly after they have occurred, allowing the conflicting nodes to quickly abort transmissions and bring the network to idle sooner, thereby reducing wasted capacity. As bandwidth increases, a message spans a smaller portion of the global bus length so network collisions can still reduce throughput significantly, especially at higher loads when collisions are more likely. See W. Bux, "Local Area Subnetworks: A Performance Comparison", IEEE Trans. on Communications, vol. Com-29, no. 10, Oct. 1981, pp. 91-100. The adaptive or random assignment access systems can be considered to be in the class of "attempt and abort".
Some systems avoid collisions by providing a delay line, as described by T. Suda et al. in "Tree LANs with Collision Avoidance: Protocol, Switch Architecture and Simulated Performance", ACM 089791-279-9/88/008/0155, or a buffer, like the register-insertion systems described by Hilal et al. and Liu et al., supra, for alleviating the corruption of data because of simultaneous access. The tree LAN system described by T. Suda et al., supra, uses the concept whereby a node in the tree can switch to one of a number of simultaneous incoming messages and thereby avoid a collision. The unselected messages are aborted, so this system is in the class of "attempt and abort". The messages which are aborted must be retransmitted to the node at a later time.
Systems which use adaptive or random assignment at high data rates usually incorporate a second collision free protocol which is used at high loads to eliminate the capacity reductions due to collisions. Such systems are classified as hybrid systems. For example, systems exist which use CSMA protocol at low loads but switch to a conflict free mode at higher load levels. Systems of this type have been described by M Skov, supra, and A. Bhargava, J. F. Kurose and D. Towsley in "A Hybrid Media Access Protocol for High-Speed Ring Networks", IEEE Jour. on Selected Areas in Communications, vol. 6, no. 6, July 1988, pp. 924-933.
As noted previously, high data rate systems are required to support integrated traffic. Many demand assignment protocol systems use a priority scheme based on upon either timing, rounds or reserved slots. Grow in U.S. Pat. No. 4,445,116 discloses a method for allocating bandwidth based upon target token rotation time (TTRT) and actual token rotation time. M. Zafirovic-Vukotic et al., supra, describe reserved slot and rounds systems for various slotted ring systems, and M Skov, supra, briefly discusses integrated traffic schemes for systems including reserved slots for reservation access in the DQDB system, polled access and slotted ring systems.
The uniframe method for integrated traffic uses assigned slots within a fixed frame. Unreserved slots can be used by a second access protocol such as token ring which is discussed by F. Ross, supra, and the proposed ANSI FDDI specifications. A second method of using uniframe is by limiting the time period of the uniframe to less than a full cycle and allowing a second access protocol to operate in the remaining period. This concept has been employed in a system known as Dynamic Resource Allocation in Metropolitan Area Networks (DRAMA) as described, for example, by K. Maly et al. in "Traffic Placement Policies for a Multi-band Network", ACM SIGCOMM '89 Symposium, Austin, Tex, Sept. 1989, pp. 94-105.
The major deficiency with these schemes is that they require either some form of master controller or an established initiation procedure in order to regulate the system. For instance, in uniframe and some timing and reservation systems, the master controller must assign slots to the synchronous traffic. Thus, a complex protocol must be established so that each node requests and knows not only its slot assignments but all other nodes' slot assignments as well so that reserved slots are not inadvertently corrupted. If a master controller is not used, as in FDDI I, the nodes must negotiate prior to ring operations. Changes to handle unanticipated traffic can not be made without halting and reinitiating ring operation. If nodes are free to reserve slots without a master controller, then capacity may be wasted or a node may hog the network.
Various CSMA collision detection (CSMA/CD) protocols are known in the prior art. See, for example, U.S. Pat. No. 4,707,829 to Pendse which discloses a CSMA/CD system that uses a unidirectional bus which is looped. Stations wait until the channel becomes idle and then transmit at the beginning of the next contention slot. The transmission is accepted if no other upstream station transmits, but if an upstream transmission is detected, the transmission is halted. Other examples of CSMA/CD systems are disclosed in U.S. Pat. No. 4,516,239 to Maxemchuk and U.S. Pat. No. 4,566,097 to Bederman. In the Bederman system, if a message arrives from upstream while a station is transmitting, the station checks priority of the incoming message. If the priority is less than or equal to the station message, the station continues to send its message. If priority is greater, the station aborts its message and forwards the incoming message. The station also aborts its message if it receives a start of a frame message which would contain synchronous data.
U.S. Pat. No. 4,549,292 to Isaman et al. discloses a method of efficiently and simultaneously transmitting both isochronous and nonisochronous data in a computer ring network. The terms "synchronous", "periodic" and "isochronous" may be used interchangeably. "Isochronous" has the additional connotation that the period is 125 microseconds, which corresponds to the frame rate used by commercial telephone systems, although Isaman et al. do not mention, nor does their system strictly require, 125 microsecond intervals. Isaman et al. use a token to designate a single station transmitting asynchronous data. As this packet propagates around the ring, any station with synchronous data may interrupt this message by inserting a control character followed by the message followed by a terminating control character. Stations upstream from the inserting station may add their synchronous data between the control characters. Alternatively, they can add another synchronous data block some other place in the asynchronous message. When the synchronous data block travels to the asynchronous sending station, it must interrupt its transmission and forward the synchronous block. It then resumes its transmission until another data block arrives or it finishes its transmission.
The Isaman et al. system lacks flexibility and limits data rate. Stations do not act independently upon detection of an idle condition on the network but must wait for a token or other control before sending asynchronous data. Other stations must buffer the incoming signal while transmitting synchronous data, and the station transmitting asynchronous data when interrupted by synchronous data must halt and then re-initiate transmission after passage of the synchronous data. The approach taken by Isaman et al. is similar to register-insertion of Hilal et al. and the Tree LAN system of Suda, described above.
A number of reservation access protocol systems have been described in the literature. See, for example, Chapter 3 of A. S. Tanenbaum, Computer Networks, 2nd Ed., Prentice-Hall, 1988. These schemes, which are also in the class of collision free protocols, generally work only for lower data rate systems, do not differentiate between types of traffic, and operate singly. U.S. Pat. No. 4,383,315 to Torng describes the concept of time slots that travel around a ring and are forwarded without interruption from a transmitter to a receiver. For synchronous traffic, time slots are reserved and may be used by the receiver to return data to the transmitter forming a full duplex circuit. For asynchronous data, a complex procedure for seizure and release of non-reserved time slots is invoked by stations having traffic.